package com.zhiyi;

import java.util.ArrayList;
import java.util.List;

public class ZhiYi {


    public static void main(String[] args) {

        String str = "applepie" ;
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("orange");
        list.add("pie");
        int[] temp = new int[str.length() + 1] ;
        System.out.println(dfs(str, 0, list, temp));
        System.out.println(dfs("applepieapple", 0, list, new int["applepieapple".length() + 1]));
        System.out.println(dfs("appie", 0, list, new int["appie".length() + 1]));
    }


    /**
     *
     * @param s 目标字符串
     * @param start  开始位置
     * @param list  字典数组
     * @param temp  临时数组
     * @return
     */
    // 利用数组做记忆化 （temp[i] == 1 代表第位置开始的子串不能分割成字典数据）
    public static boolean dfs(String s, int start, List<String> list, int[] temp ){
        if (s.length() == start){
            return true ;
        }
        for (int end = start +1 ; end <= s.length(); end ++ ) {
            String tempStr = s.substring(start, end);
            if (temp[end] == 1){
                continue;
            }
            if (list.contains(tempStr)){
                if (dfs(s, end, list, temp) ){
                    return true ;
                }else {
                    temp[end] = 1 ;
                }
            }
        }
        return false ;
    }
}
